package com.bang.study.day02;

import com.bang.study.day01.InsertionSort;
import com.bang.study.util.ArrayUtil;
import com.bang.study.util.TestUtil;
import org.apache.commons.lang3.ArrayUtils;

/**
 * @Auther: Bang
 * @Date: 2019/9/21 0021 10:18
 * @Description: 双路快速排序
 * @link https://www.cnblogs.com/deng-tao/p/6523433.html
 * @描述:
 *当我们排序的是一个近乎有序的序列时，快速排序会退化到一个O(n^2)级别的排序算法，
 * 而对此的改进就是引入了随机化快速排序算法；但是当我们排序的是一个数值重复率非常高的序列时，
 * 此时随机化快速排序算法就不再起作用了，而将会再次退化为一个O(n^2)级别的排序算法
 */
public class QuickSortV3 {


    /**
     * 快速排序
     *
     * @param arr
     */
    public static void sort(Integer[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 对数组arr[l,r]快速排序
     * @param arr
     * @param l
     * @param r
     */
    private static void  quickSort(Integer[] arr, int l, int r) {
        if (r - l <= 16) {
            InsertionSort.insertSort(arr, l, r);
        }
        else{
          int p= partition(arr,l,r);
            quickSort(arr, l, p - 1);
            quickSort(arr, p+1, r);
        }
    }

    /**
     * 将arr进行分割,返回数组中心点 pivot
     *   arr[l..pivot-1] < arr[pivot] < arr[pivot+1, r]
     * @param arr
     * @param l 左边界
     * @param r 右边界
     * @return 数组中心点
     */
    private static int partition(Integer[] arr, int l, int r) {
        // 随机取数组中的元素  解决数组趋于有序的情况时,快速排序退化为O(n2)的情况
        int random = (int) (Math.random() * (r - l + 1) + l);
        // 和left进行交换
        swap(arr, l, random);
        int pivot = arr[l];

         // arr[l+1 ... i) <= pivot ; arr(j ... r] >= pivot
        int i = l + 1, j = r;
       while (true){
           while (i<=r&&arr[i]<pivot){
               i++;
           }
           while (j<=l+1&&arr[j]>pivot){
               j--;
           }
           if (i>j) {
               break;
           }else {
               swap(arr, i, j);
               i++;
               j--;
           }
       }
        swap(arr, l, j);
        return j;
    }

    private static void  swap(Integer[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] array = ArrayUtil.generateRandomArray(1000000, 0, 2);
        TestUtil.test(MergeSort.class, ArrayUtils.clone(array));

        ArrayUtil.printArray(array,10);
        long start = System.nanoTime();
        sort(array);
        long end = System.nanoTime();
        double v = (end - start) / 1000000000.0;
        System.out.println(String.format("耗时: %s 秒", v));
        ArrayUtil.printArray(array, 10);

    }
}
